package com.leetcode.二叉树.广度优先;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 * 
 * @author LZF
 *
 */
public class L429N叉树的层序遍历 {
	/**
	 * 跟普通的迭代算法一样，只不过不止左右子树两个孩子，因此在入队的时候用for来遍历每个节点的孩子就行了
	 */
	public List<List<Integer>> levelOrder(Node root) {
		// 二维结果容器
		List<List<Integer>> resList = new ArrayList<List<Integer>>();
		Queue<Node> que = new LinkedList<>();// 队列
		if (root != null)
			que.offer(root);// 入队(在队尾)
		while (!que.isEmpty()) {
			int len = que.size();// 当前层数的节点数
			List<Integer> result = new ArrayList<Integer>();// 添加放该层的结果容器（一维）
			while (len > 0) {
				Node node = que.poll();// 出队（在队头）
				result.add(node.val);
				List<Node> nodes = node.children;
				//孩子们入队
				for(int i = 0;i < nodes.size();i++) {
					if(nodes.get(i) != null) que.offer(nodes.get(i));
				}
				len--;
			}
			resList.add(result);
		}
		return resList;

	}

//树的定义
	class Node {
		public int val;
		public List<Node> children;

		public Node() {
		}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val, List<Node> _children) {
			val = _val;
			children = _children;
		}
	}
}
